https://leetcode-cn.com/problems/4sum/

这个解法用时只打败了20%的人，但是内存消耗打败了99%

是根据三数之和改的

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        #排序
        nums.sort()
        #返回值
        ret = []
        lenNums = len(nums)
        # print('nums',nums)
        for i in range(lenNums-3):
            # print('i',i)
            val = nums[i]
            #i的值>target 无解
            if val > 0 and target > 0 and val > target:
                break
            #判断是否和上一位重复
            if i > 0 and val == nums[i-1]:
                continue
            for o in range(i + 1,lenNums - 2):
                # print('o',o)
                val2 = nums[o]
                if val2 > 0 and target > 0 and val + val2 > target:
                    break
                #判断是否和上一位重复
                if o > i + 1 and val2 == nums[o-1]:
                    continue
            
                l = o + 1
                r = lenNums - 1
                while l < r:
                    # print('l',l,'r',r)
                    #末位<0 无解
                    # if nums[r] < target:
                    #     break
                    if val + val2 + nums[l] + nums[r] == target:
                        ret.append((
                            val, val2, nums[l] , nums[r]
                        ))
                        #判断下一位是否和当前相同，若相同则跳过
                        while l < r and nums[r] == nums[r-1]:
                            r -= 1
                        while l < r and nums[l] == nums[l+1]:
                            l += 1
                        #寻找下一个
                        r -= 1
                        l += 1
                    elif val + val2 + nums[l] + nums[r] > target:
                        #当前值偏大，右侧想左移动
                        r -= 1
                    else:
                        #当前值偏小，左侧向右移动
                        l += 1
        return ret